package 数组;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目：
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，
 * 使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 */
public class 数组中和为0的三个数 {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List list = new ArrayList<List<Integer>>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]>0) {
                    break;
                }
                if (i>0 &&nums[i]==nums[i-1]) {
                    continue;
                }
                int index = i;
                int left = i+1;
                int right = nums.length-1;
                while(left<right) {
                    if (nums[index]+nums[left]+nums[right]>0) {
                        right--;
                    }else if (nums[index]+nums[left]+nums[right]<0) {
                        left++;
                    }else {
                        list.add(Arrays.asList(nums[index],nums[left],nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                    }
                }
            }
            return list;
        }
    }
}
